package com.gorkr.hot100.simple;

/**
 * @author 张心宇 <zhangxinyu20@kuaishou.com>
 * Created on 2022-12-21
 */

public class E543 {
    private int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        traverse(root);
        return max;
    }
    // 遍历整棵树 找到最长的路径
    private void traverse(TreeNode root){
        if (root==null){
            return;
        }

        max = Math.max(max, trace(root));

        traverse(root.left);
        traverse(root.right);
    }

    // 以root为根的树的左右树深和（就是经过root最长路径）
    public int trace(TreeNode root) {
        if(root==null){
            return 0;
        }
        return maxLeng(root.left) + maxLeng(root.right);
    }
    // 树深
    private int maxLeng(TreeNode root){
        if(root == null){
            return 0;
        }
        return  Math.max(maxLeng(root.left), maxLeng(root.right)) + 1;
    }
}
